package Hot100;

import java.util.*;

/**
 * @author zhangmin
 * @create 2022-01-12 21:42
 */
public class findAnagrams438 {

    /**
     * 438. 找到字符串中所有字母异位词
     * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
     * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）
     * 滑动窗口
     * */
    public List<Integer> findAnagrams(String s, String p) {
        if (s.length()<p.length()) return new ArrayList<>();
        Map<Character,Integer> windows=new HashMap<>(),need=new HashMap<>();
        for (char c:p.toCharArray()) {
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left=0,rigth=0;
        int valid=0;//记录窗口内达到需要个数的字符的个数
        List<Integer> res=new LinkedList<>();
        while (rigth<s.length()){
            //c为要加入窗口的字符
            char c=s.charAt(rigth);
            rigth++;
            //更新窗口内状态
            if (need.containsKey(c)){
                windows.put(c,windows.getOrDefault(c,0)+1);
                if (windows.get(c).equals(need.get(c))){
                    valid++;
                }
            }
            //缩小左窗口
            while (rigth-left>=p.length()){
                if (valid==need.size()&&rigth-left==p.length()){
                    //窗口符合收缩条件
                    res.add(left);
                }
                char d=s.charAt(left); left++;
                if (need.containsKey(d)){
                    if (windows.getOrDefault(d,0).equals(need.get(d))){
                        valid--;
                    }
                    windows.put(d,windows.getOrDefault(d,0)-1);
                }
            }
        }
        return res;
    }
}
